package xyf.p09.bfs_dfs;

import java.util.*;

/**
 * ClassName: M0401_FindWhetherExistsPath
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:19 AM
 * Version: 1.0
 **/
public class M0401_FindWhetherExistsPath
{
    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target)
    {
        Map<Integer, List<Integer>> graphMap = new HashMap<>();
        for (int i = 0; i < graph.length; i++)
        {
            List<Integer> list = graphMap.get(graph[i][0]);
            if (null == list)
            {
                list = new ArrayList<>();
                graphMap.put(graph[i][0], list);
            }

            list.add(graph[i][1]);
        }
        boolean[] visited = new boolean[n];

        return dfs(graphMap, start, target, visited);
    }

    private boolean dfs(Map<Integer, List<Integer>> graphMap, int start, int target, boolean[] visited)
    {
        List<Integer> list = graphMap.get(start);
        if (list == null || list.size() == 0)
        {
            return false;
        }

        for (Integer i : list)
        {
            if (i == target)
            {
                return true;
            }
            if (visited[i])
            {
                continue;
            }
            visited[i] = true;

            if (dfs(graphMap, i, target, visited))
            {
                return true;
            }
            visited[i] = false;
        }
        return false;
    }
}